Міністерство освіти та науки, молоді та спорту України
Національний університет «Львівська політехніка»
Курсовий проект
на тему:
«Дослідження алгоритму вибіркових переміщень»
ЗМІСТ
1. ВСТУП
2. ОГЛЯД ЛІТЕРАТУРНИХ ДЖЕРЕЛ
2.1. Поняття комбінаторного розміщення елементів
2.2. Ідеальні кільцеві в’язанки як одновимірна нееквідистантні структура
2.3 Основні відомості про алгоритм вибіркових переміщень.
3. СИСТЕМНИЙ АНАЛІЗ
3.1. Аналіз проблеми
3.2. Основні пункти методу
3.3. Критерій заповнення двовимірних нееквідистантних структур
4. ПОБУДОВА ІКВ МЕТОДОМ ВИБІРКОВИХ ПЕРЕМІЩЕНЬ
5. ПРОГРАМНА РЕАЛІЗАЦІЯ
5.1. Постановка задачі
5.2. Середовище розробки програми
5.3. Опис програми
ВИСНОВКИ
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
ДОДАТОК
1.ВСТУП
Нехай задана множина ={}, елементів і задана операція «#», що здійснюється над елементами цієї множини. Тоді n- в’язанкою за операцією «#» називається впорядкована сукупність n – елементів, кожен з яких утворюється застосуванням заданої операції між наборами послідовно розміщених елементів даної сукупності.
Отже можна вважати, що n- в’язанка породжує множину , де , - новоутворена множина. Кожен з елементів має не менше 2-х полюсів, які є його умовними входами і виходами і вказують на порядок виконання операції.
Порядок n- в’язанки – це кількість n базових елементів, що входять до її складу. Кількість новоутворених n- елементів визначається її структурою та порядком.
Одновимірна n- в’язанка утворюється на упорядкованій сукупності елементів, які є одновимірними числовими об’єктами (числа, відрізки), дво та більше вимірна відповідно на сукупності елементів, які є відповідно дво або більше вимірними (наприклад вектори t- вимірного простору, де t).
Одновимірні в’язанки складаються з чисел, багатовимірні – з упорядкованих числових наборів:
1 2 10 19 4 7 9 5
Рис.1 Одновимірна числова в’язанка
Рис.2 Двовимірна числова в’язанка
Числова в’язанка, утворена з елементів, які у свою чергу також є в’язанками, називається комбайном в’язанок, а їх упорядкована сукупність – гіперкомбайном.
Числові в’язанки поділяються на ідеальні та неідеальні. Оскільки алгоритм вибіркових переміщень використовується тільки для побудови ідеальних кільцевих в’язанок(ІКВ), то саме їх ми надалі розглянемо детально.
2. ОГЛЯД ЛІТЕРАТУРНИХ ДЖЕРЕЛ
2.1. Поняття комбінаторного розміщення елементів
В комбінаториці, розміщенням із n елементів по m, або впорядкованою (n, m) вибіркою із множини M (потужність n, m≤n) називають довільний кортеж що складається із m попарно відмінних елементів. Розміщення можна розглядати як різнозначну функцію f: , для якої .
Кількість розміщень із n по m позначається як або P(n,m) і обчислюється за наступною формулою:
Розміщення з повтореннями
Розміщенням з повтореннями із n елементів по m або дворядкованою (n, m) вибіркою з поверненнями називається довільний кортеж елементів множини M, для якого |M| = n.
Кількість можливих розміщень з повтореннями із n елементів по m дорівнює n піднесене до степеня m:
Наприклад, із цифр 1, 2, 3, 4 можна скласти трьохзначних числа.
Поняття «ІКВ» та його визначення.
Ідеальна кільцева в’язанка – це упорядкована циклічна послідовність чисел
,
на якій всі можливі кільцеві суми, які утворюють значення чисел натурального ряду від 1 до Sn=n(n — 1). Кільцевою сумою називається сума будь-якої кількості (від 1 до n-1) послідовно розміщених елементів циклічної n-послідовності. Наприклад, якщо вибрати циклічну послідовність з чисел 1,4,2, то з них можна утворити натуральний ряд чисел від 1 до =7:
1=1;
2=2;
3=2+1;
4=4;
5=4+1;
6=2+4;
7=1+4+2;
Цей ряд можна продовжити, обираючи перший елемент для початку відліку та обходячи кільцеву схему більше одного разу, наприклад:
8=1+4+2+1;
Отже, наведена вище цикліч...
